package com.desin.modle.sorts;

import java.util.Arrays;

public class MyMergeSort {
    public int num;
    public void sort(int[] data){
        mergeSort(data,0,data.length-1);
    }

    private void mergeSort(int[] data, int start, int end) {
        if(start>=end){
            return;
        }
        int mid = (start+end)/2;
        mergeSort(data,start,mid);
        mergeSort(data,mid+1,end);
        merge(data,start,mid,end);
    }

    private void merge(int[] data, int start,int mid, int end) {
        int[] temp = new int[end-start+1];
        int left=start;
        int right=mid+1;
        int tempIndex=0;
        while(left<=mid&&right<=end){
            if(data[left]<data[right]){
                temp[tempIndex]=data[left];
                left++;
            }else{
                num += (mid - left + 1);//逆序对的表示
                temp[tempIndex]=data[right];
                right++;
            }
            tempIndex++;
        }
        if(left<=mid){
            for(int i=left;i<=mid;i++){
                temp[tempIndex]=data[i];
                tempIndex++;
            }
        }
        if(right<=end){
            for(int i=right;i<=end;i++){
                temp[tempIndex]=data[i];
                tempIndex++;
            }
        }
        for(int i=0;i<=tempIndex-1;i++){
            data[start+i]=temp[i];
        }
    }

    public static void main(String[] args) {
        MyMergeSort myMergeSort = new MyMergeSort();
        int[] arrays = new int[] {1,3,2,3,1};
        myMergeSort.sort(arrays);
        System.out.println(Arrays.toString(arrays));
        System.out.println("结果:" + myMergeSort.num);
    }
}
